package leetcode_1000;

import java.util.Arrays;

/**
 *@author 周杨
 *BagOfTokens_948 给定一个Int数组和输出power 每次要么购买其中的商品 花掉钱 +1积分 要么花掉1积分 加上钱
 *describe:用贪心算法 双指针 AC 
 *2018年11月25日 下午8:09:23
 */
public class BagOfTokens_948 {
	public static void main(String[] args) {
		BagOfTokens_948 test=new BagOfTokens_948();
		System.out.println(test.bagOfTokensScore(new int[] {100,200,300,400}, 200));
	}
	
	public int bagOfTokensScore(int[] tokens, int P) {
		if(tokens.length==0)
			return 0;
        Arrays.sort(tokens);
        if(P<tokens[0]) return 0;//买不起
        P-=tokens[0];
        int res=1,left=1,right=tokens.length-1;
        while(left<=right) {
        	if(P>=tokens[left]) {
        		P-=tokens[left++];
        		res++;
        	}
        	else {
        		if(left==right)
        			return res;//不买了
        		res--;
        		P+=tokens[right--];
        	}
        }
        return res;
    }
}
